The example of a `while' loop that printed the elements of a list of
numbers can be written recursively. Here is the code, including an
expression to set the value of the variable `animals' to a list.
If you are using Emacs 20 or before, this example must be copied to
the `*scratch*' buffer and each expression must be evaluated there.
Use `C-u C-x C-e' to evaluate the `(print-elements-recursively
animals)' expression so that the results are printed in the buffer;
otherwise the Lisp interpreter will try to squeeze the results into the
one line of the echo area.
Also, place your cursor immediately after the last closing
parenthesis of the `print-elements-recursively' function, before the
comment. Otherwise, the Lisp interpreter will try to evaluate the
comment.
If you are using Emacs 21 or later, you can evaluate this expression
directly in Info.
(setq animals '(gazelle giraffe lion tiger))
(defun print-elements-recursively (list)
"Print each element of LIST on a line of its own.
Uses recursion."
(if list ; do-again-test
(progn
(print (car list)) ; body
(print-elements-recursively ; recursive call
(cdr list))))) ; next-step-expression
(print-elements-recursively animals)
The `print-elements-recursively' function first tests whether there
is any content in the list; if there is, the function prints the first
element of the list, the CAR of the list. Then the function `invokes
itself', but gives itself as its argument, not the whole list, but the
second and subsequent elements of the list, the CDR of the list.
Put another way, if the list is not empty, the function invokes
another instance of code that is similar to the initial code, but is a
different thread of execution, with different arguments than the first
instance.
Put in yet another way, if the list is not empty, the first robot
assemblies a second robot and tells it what to do; the second robot is
a different individual from the first, but is the same model.
When the second evaluation occurs, the `if' expression is evaluated
and if true, prints the first element of the list it receives as its
argument (which is the second element of the original list). Then the
function `calls itself' with the CDR of the list it is invoked with,
which (the second time around) is the CDR of the CDR of the original
list.
Note that although we say that the function `calls itself', what we
mean is that the Lisp interpreter assembles and instructs a new
instance of the program. The new instance is a clone of the first, but
is a separate individual.
Each time the function `invokes itself', it invokes itself on a
shorter version of the original list. It creates a new instance that
works on a shorter list.
Eventually, the function invokes itself on an empty list. It creates
a new instance whose argument is `nil'. The conditional expression
tests the value of `list'. Since the value of `list' is `nil', the
`if' expression tests false so the then-part is not evaluated. The
function as a whole then returns `nil'.
When you evaluate `(print-elements-recursively animals)' in the
`*scratch*' buffer, you see this result:
giraffe
gazelle
lion
tiger
nil
File: emacs-lisp-intro.info, Node: Recursive triangle function, Next: Recursion with cond, Prev: Recursion with list, Up: Recursion
Recursion in Place of a Counter
-------------------------------
The `triangle' function described in a previous section can also be
written recursively. It looks like this:
(defun triangle-recursively (number)
"Return the sum of the numbers 1 through NUMBER inclusive.
Uses recursion."
(if (= number 1) ; do-again-test
1 ; then-part
(+ number ; else-part
(triangle-recursively ; recursive call
(1- number))))) ; next-step-expression
(triangle-recursively 7)
You can install this function by evaluating it and then try it by
evaluating `(triangle-recursively 7)'. (Remember to put your cursor
immediately after the last parenthesis of the function definition,
before the comment.) The function evaluates to 28.
To understand how this function works, let's consider what happens
in the various cases when the function is passed 1, 2, 3, or 4 as the
value of its argument.
* Menu:
* Recursive Example arg of 1 or 2::
* Recursive Example arg of 3 or 4::
File: emacs-lisp-intro.info, Node: Recursive Example arg of 1 or 2, Next: Recursive Example arg of 3 or 4, Prev: Recursive triangle function, Up: Recursive triangle function
An argument of 1 or 2
.....................
First, what happens if the value of the argument is 1?
The function has an `if' expression after the documentation string.
It tests whether the value of `number' is equal to 1; if so, Emacs
evaluates the then-part of the `if' expression, which returns the
number 1 as the value of the function. (A triangle with one row has
one pebble in it.)
Suppose, however, that the value of the argument is 2. In this case,
Emacs evaluates the else-part of the `if' expression.
The else-part consists of an addition, the recursive call to
`triangle-recursively' and a decrementing action; and it looks like
this:
(+ number (triangle-recursively (1- number)))
When Emacs evaluates this expression, the innermost expression is
evaluated first; then the other parts in sequence. Here are the steps
in detail:
Step 1 Evaluate the innermost expression.
The innermost expression is `(1- number)' so Emacs decrements the
value of `number' from 2 to 1.
Step 2 Evaluate the `triangle-recursively' function.
The Lisp interpreter creates an individual instance of
`triangle-recursively'. It does not matter that this function is
contained within itself. Emacs passes the result Step 1 as the
argument used by this instance of the `triangle-recursively'
function
In this case, Emacs evaluates `triangle-recursively' with an
argument of 1. This means that this evaluation of
`triangle-recursively' returns 1.
Step 3 Evaluate the value of `number'.
The variable `number' is the second element of the list that
starts with `+'; its value is 2.
Step 4 Evaluate the `+' expression.
The `+' expression receives two arguments, the first from the
evaluation of `number' (Step 3) and the second from the evaluation
of `triangle-recursively' (Step 2).
The result of the addition is the sum of 2 plus 1, and the number
3 is returned, which is correct. A triangle with two rows has
three pebbles in it.
File: emacs-lisp-intro.info, Node: Recursive Example arg of 3 or 4, Prev: Recursive Example arg of 1 or 2, Up: Recursive triangle function
An argument of 3 or 4
.....................
Suppose that `triangle-recursively' is called with an argument of 3.
Step 1 Evaluate the do-again-test.
The `if' expression is evaluated first. This is the do-again test
and returns false, so the else-part of the `if' expression is
evaluated. (Note that in this example, the do-again-test causes
the function to call itself when it tests false, not when it tests
true.)
Step 2 Evaluate the innermost expression of the else-part.
The innermost expression of the else-part is evaluated, which
decrements 3 to 2. This is the next-step-expression.
Step 3 Evaluate the `triangle-recursively' function.
The number 2 is passed to the `triangle-recursively' function.
We know what happens when Emacs evaluates `triangle-recursively'
with an argument of 2. After going through the sequence of
actions described earlier, it returns a value of 3. So that is
what will happen here.
Step 4 Evaluate the addition.
3 will be passed as an argument to the addition and will be added
to the number with which the function was called, which is 3.
The value returned by the function as a whole will be 6.
Now that we know what will happen when `triangle-recursively' is
called with an argument of 3, it is evident what will happen if it is
called with an argument of 4:
In the recursive call, the evaluation of
(triangle-recursively (1- 4))
will return the value of evaluating
(triangle-recursively 3)
which is 6 and this value will be added to 4 by the addition in the
third line.
The value returned by the function as a whole will be 10.
Each time `triangle-recursively' is evaluated, it evaluates a
version of itself--a different instance of itself--with a smaller
argument, until the argument is small enough so that it does not
evaluate itself.
Note that this particular design for a recursive function requires
that operations be deferred.
Before `(triangle-recursively 7)' can calculate its answer, it must
call `(triangle-recursively 6)'; and before `(triangle-recursively 6)'
can calculate its answer, it must call `(triangle-recursively 5)'; and
so on. That is to say, the calculation that `(triangle-recursively 7)'
makes must be deferred until `(triangle-recursively 6)' makes its
calculation; and `(triangle-recursively 6)' must defer until
`(triangle-recursively 5)' completes; and so on.
If each of these instances of `triangle-recursively' are thought of
as different robots, the first robot must wait for the second to
complete its job, which must wait until the third completes, and so on.
There is a way around this kind of waiting, which we will discuss in
